package org.example.sword2offer.primary;

import java.util.Stack;

/**
 * @author: lynn
 * @Descript: leetcode 25 k个一组翻转链表
 * @date: 2021/7/8 18:13
 * @version: 1.0
 */
public class Q87_ReverseKListNode {
    public static void main(String[] args) {
        ListNode listNode=new ListNode(1);
        listNode.next=new ListNode(2);
        listNode.next.next=new ListNode(3);
        listNode.next.next.next=new ListNode(4);
        listNode.next.next.next.next=new ListNode(5);
        Q87_ReverseKListNode reverseKListNode=new Q87_ReverseKListNode();
        reverseKListNode.reverseKGroup(listNode,3);
    }

    //fixme https://www.bilibili.com/video/BV1QT4y1F7SD?from=search&seid=1855626387954071726
    public ListNode reverseKGroup(ListNode head, int k) { // fixme k个一组翻转链表
        if (head==null|| head.next==null) return head;
        ListNode dummy=new ListNode(0);
        ListNode curNode=head;
        Stack<ListNode> stack=new Stack();
        int localk=k;
        while (curNode!=null && localk>0 ){
            localk--;
            stack.push(curNode);
            curNode=curNode.next;
        }
        if (stack.size()<k) return  head; //fixme 为什么是head，不是curNode，第二轮递归的时候，就是head，此时curNode已经飘到最后了
        ListNode pre=dummy; //fixme 防止dummy位置发生偏移
        while (stack.size()>0){
            pre.next=stack.pop();
            pre=pre.next;
        }
        pre.next=reverseKGroup(curNode,k);
        return dummy.next;
    }


    private static class ListNode{
        ListNode next;
        int val;
        ListNode(int val){
            this.val=val;
        }
    }
}
